package com.wwz.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

//给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。
public class LeetCode1447 {

    @Test
    public void test() {
        System.out.println(simplifiedFractions(6));
    }

    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                // 检查是否可构成最简分数
                if (check(i, j)) {
                    // 构造结果
                    ans.add(build(i, j));
                }
            }
        }
        return ans;
    }

    private boolean check(int i, int j) {
        // 看两个数有没有公约数
        // 我们可以求最大公约数，如果是1，说明可以组成最简分数，比如2和3
        return gcd(i, j) == 1;
    }

    private int gcd(int i, int j) {
        // 求最大公约数
        return j % i == 0 ? i : gcd(j % i, i);
    }

    private String build(int i, int j) {
        return i + "/" + j;
    }
}
